﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    public static class Ex_9_8
    {
        static bool UseDynamicProgramming = true;

        public static int GetNumWays(int Demomination, int NumCents)
        {
            int nextDenom = 0;
            switch (Demomination)
            {
                case 25:
                    nextDenom = 10;
                    break;
                case 10:
                    nextDenom = 5;
                    break;
                case 5:
                    nextDenom = 1;
                    break;
                case 1:
                    return 1;
            }

            int NumWays = 0;
            for (int i = 0; i * Demomination <= NumCents; i++)
            {
                NumWays += GetNumWays(nextDenom, NumCents - (i * Demomination));
            }

            return NumWays;
        }
    }
}
